/* 背包问题 */

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct TGoods
{
	int weight;
	int value;

	TGoods(int w, int v)
		: weight(w)
		, value(v)
	{
	}
};

int main(void)
{
	constexpr int N = 4;
	TGoods goods[N] = {
		{ 1, 4 },
		{ 2, 6 },
		{ 3, 12 },
		{ 2, 7 }
	};
	const int totalWeight = 6;

	/* 设问题模型为F(i, j) = 取最多i件商品，总重要不超过j，得到的总价值
	* 第i件商品可取，可不取。
	* 不取第i件商品时，F(i, j) = F(i - 1, j)
	* 取第i件商品时，前i - 1件商品总重要不能超过j - weight[i]，即
	* F(i, j) = F(i - 1, j - weight[i]) + value[i]，则有：
	* F(i, j) = max(F(i - 1, j), F(i - 1, j - weight[i]) + value[i]) */

	int finalValue[totalWeight + 1]{ 0 };
	vector<int> vecGood[totalWeight + 1];

	//只取第0件物品的情况
	for (int j = 0; j <= totalWeight; j++)
	{
		if (goods[0].weight <= j)
		{
			finalValue[j] = goods[0].value;
			vecGood[j].push_back(0);
		}
		else
		{
			finalValue[j] = 0;
			vecGood[j].push_back(-1);
		}
	}

	for (int i = 1; i < N; i++)
	{
		for (int j = totalWeight; j >= 0; j--)
		{
			if (goods[i].weight > j)
			{
				continue;
			}

			int max1 = finalValue[j];
			int max2 = finalValue[j - goods[i].weight] + goods[i].value;

			if (max1 > max2)
			{
				finalValue[j] = max1;
			}
			else
			{
				finalValue[j] = max2;
				vecGood[j].assign(vecGood[j - goods[i].weight].begin(), vecGood[j - goods[i].weight].end());
				vecGood[j].push_back(i);
			}
		}
	}

	cout << "The maximum value is: "<< finalValue[totalWeight] << "\n";
	cout << "And we select goods index are: ";
	for_each(vecGood[totalWeight].begin(), vecGood[totalWeight].end(), 
		[](int e) -> void {
		if (e != -1)
		{
			cout << e << " ";
		}
	});

	cout << endl;
}

